Various digital communications applications and standards like 802.16, WiMax, and DVB-T, among others, use Fourier Transforms as part of Orthogonal Frequency Division Multiplexing (“OFDM”) systems. Various implementations of Fourier Transforms are provided in a set of algorithms called Fast Fourier Transforms (“FFTs”). FFT algorithms can be implemented using radix-2, radix-4, etc. algorithms. Both the forward FFT and the inverse FFT (“IFFT”) change the order of data frames provided as input to these algorithms. For example, if the input data to an FFT block is in natural order, as for Decimation In Frequency (“DIF”) type FFTs, the output from the FFT block is in bit- or digit-reversed order. Similarly, if the input data to the FFT block is provided in bit- or digit-reversed order, as for Decimation in Time (“DIT”) type FFTs, then the output data of FFT block is in natural order. Radix-2 DIF algorithms output data in bit-reversed order, while for higher radix implementations, digit-reversed ordering is the form of the output.
Bit-reversed order is based on a binary number representation of an index. A 16-point FFT block has 16 data values with indices 0, 1, 2, 3 . . . , 14, 15. These indices are represented in binary as 0000, 0001, 0010, . . . , 1110, 1111. A bit-reversed indexing reverses the order of such bits. So a natural index of 0000, 0001, 0010, . . . , 1110, 1111 has a corresponding bit-reversed order of 0000, 1000, 0100, . . . , 0111, 1111 which translates in decimal to indices of 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.
Digit-reversed ordering may be thought of as a generalization of bit-reversed ordering for an arbitrary radix-k, where the order of digits are reversed for a radix-k representation of index n, for k and n positive even integers. Digit reversing for radix-4 may be thought of as rearranging of groups of 2 bits in a binary representation, so index bits are reversed in groups of 2 bits. Thus, for example, a 0110 in binary after digit-reversed ordering for radix-4 would be 1001, as the group of two bits on the far right would effectively be swapped in place for the group of two bits on the far left. Similarly the reverse ordering in radix-8 may be in groups of 3 bits, and so on.